/**
 * 选择排序（Selection sort）
 *
 * ---------------------------------
 * 文档查看: /document/algo/sort_selection.md
 * 2021-01-22
 */

const TimeTool = require('./utils/TimeTool')

/**
 * 方法一:
 * @param {*} array
 */
function SortSelection1(array) {
  if (!array) return null
  const length = array.length || 0
  if (length <= 1) return array
  for (let i = 0; i < length - 1; i++) {
    for (let j = i + 1; j < length; j ++) {
      if (array[i] > array[j]) {
        const temp = array[i]
        array[i] = array[j]
        array[j] = temp
      }
    }

    // let iString = 'i =' + i + ' array=>'
    // for (let k = 0; k < length; k++) {
    //   iString += ' ' + array[k]
    // }
    // console.log(iString)
  }
  return array
}

/**
 * 方法二: 较少交换地址值
 * @param {*} array
 */
function SortSelection2(array) {
  if (!array) return null
  const length = array.length || 0
  if (length <= 1) return array
  for (let i = 0; i < length - 1; i++) {
    let min = i;

    for (let j = i + 1; j < length; j++) {
      min = array[min] > array[j] ? j : min;
    }

    if (min != i) {
      swap(array, min, i)
    }

    // let iString = 'i =' + i + ' array=>'
    // for (let k = 0; k < length; k++) {
    //   iString += ' ' + array[k]
    // }
    // console.log(iString)
  }
  return array;
}

function swap(array, x, y) {
  let temp = array[x]
  array[x] = array[y]
  array[y] = temp
  return array
}

// const Data = [1, 4, 9, 5, 4, 3]
const Data = [4,3,2]

const array1 = JSON.parse(JSON.stringify(Data))
TimeTool(()=> {
  console.log('\n 11 array=', array1)
  console.log(SortSelection1(array1))
})

const array2 = JSON.parse(JSON.stringify(Data))
TimeTool(()=> {
  console.log('\n 22 array=', array2)
  console.log(SortSelection2(array2))
})